package com.rran.study.algorithm.easy.day07;

import com.rran.study.algorithm.medium.day06.ListNode;

import java.util.Stack;

/**
 * @author yy
 * @Type Solution.java
 * @Desc 反转一个单链表。
 * <p>
 * 示例:
 * <p>
 * 输入: 1->2->3->4->5->NULL
 * 输出: 5->4->3->2->1->NULL
 * <p>
 * 进阶:
 * 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 * @date 2020/9/9
 */
public class Solution {

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(9);
        ListNode l5 = new ListNode(9);
        l1.setNext(l2);
        l2.setNext(l3);
        l3.setNext(l4);
        l4.setNext(l5);
        Solution solution = new Solution();
        ListNode result = solution.reverseList(l1);
        result.printListNode(result);
    }

    //运用stack
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> list = new Stack<>();
        list.add(head);
        ListNode other = head.getNext();
        while (other!= null) {
            list.add(other);
            other = other.getNext();
        }

        ListNode result = new ListNode();
        ListNode other2 = result;
        while (list.size()>0){
            ListNode listNode = list.pop();
            ListNode listNode1 = new ListNode(listNode.getVal());
            other2.setNext(listNode1);
            other2 = other2.getNext();
        }
        return result.getNext();
    }
}
